1. Field of the Invention
The present invention relates to a join operation processing system in a relational model, particularly to a join operation processing system in the relational model where, on the occasion of the join operation which generates a new table linking the tuples or sets of related information of a plurality of pertinent tables focusing on the common field between the tables or a plurality of common fields between tables having a plurality of fields, the minimum extraction range for determining the tuples to be processed is determined in regard to the join field or the plurality of join fields for each table which is considered as the object of the join operation and thereby, the operation rate of the system is improved by omitting, as far as possible, the processings which refer to unwanted data.
2. Description of the Prior Art
In the data processing system utilizing a data base, each set of data is often held as table such as shown in FIGS. 1(A), (B).
In FIG. 1, 1 indicates, for example, an employee A table (EMPA) listing information relating to employees. The employee A table 1 provides or comprises, for example, the fields 2-1 to 2-4 for employee number (ENO), employee name (NAME), department number (DNO) and salary (SAL), respectively. In the employee A table 1, for example, "70101, Yamada, 005, a.sub.1 " are respectively together called a tuple and table 1 provides tuples 3-1, 3-2, . . . .
In FIG. 1, 4 indicates a department A table (DEPTA) which is one of several possible tables relating to department. The department A table 4 provides or comprises, for example, the fields 5-1 to 5-3 for the department number (DNO), department name (DNAME) and location (LOC), respectively, and also provides plurality of tuples 6-1, 6-2, . . . .
The tuples in the employee A table 1 and the department A table 4 are often or usually not sorted in an ascending sequence or descending sequence with respect to the field which is going to be join processed or related by another table, for example the department number (DNO) fields 2-3 and 5-1 of table 1 and table 4 are not in any particular logical order. Of course, it is natural that a sorted relationship between tuples is the most desirable for execution of the join processing operation in order to minimize searching and the present invention uses such sorted results.
In general, although not sorted differently from above random condition, certain kinds of table, among those indicated, have an index 7 or index table for the field used with a high frequency as shown in FIG. 1(C).
Namely, the index table 7 indicated in FIG. 1(C), in the example, is an index prepared for the department field (DNO) 2-3 in the employee A table 1 in order of department number. The index of this kind has information pairs of 8-1, 8-2, . . . and each information pair provides, in the case of FIG. 1(C), a department number (DNO) and a tuple indentifier, for example, the addresses *.sub.1, *.sub.2, . . . of where the tuple with the pertinent department number exists in the employee A table 1. In the pertinent index table, as shown in FIG. 1(C), the department number (DNO) is held, for example, in an ascending order and if the desired department number (DNO) i is designated, it is possible to directly extract the corresponding address information pair 8-i from the index table 7. Existence of such an index 7 is equivalent to having a part of the department field (DNO) 2-3 in the employee A table 1 sorted and the present invention also uses an index of this kind.
The join processing in the present invention may be thought of as corresponding to the generation of a table having a new tuple, for example, by linking equivalent tuples, that is, tuples having a department number (DNO) in the employee A table 1 with the tuple having the department number (DNO) in the department A table 4.
When performing the join processing operation, for example, it is determined whether the department number "020" corresponding to the department number "020" in the department A table 4 exists in the employee A table 1 by using the sorted table or index as explained above. When such department number exists, the tuples, for example 6-3, 3-2 having the department number "020" of both tables are linked. For the above-mentioned join processing, it is very effective to utilize the sorted table or index as explained above, but, for example, when the user desires that the department numbers (DNO) having a value "10" to "30" should be joined, join processing is only required for tuples within the range of pertinent values and the processing speed is still unduly limited if processing is not carried out by limiting the tuples considered as an object of the join processing operation.
Presently the following processing systems are used within the join processing field.
(A) A system for obtaining an answer by sequentially scanning an index which exists for the join of fields of pertinent tables. PA0 (B) A system for obtaining an answer by sorting each tuple based on the join field when the index does not exist and by scanning the sorted result. PA0 (C) A system which combines systems (A) and (B) PA0 (D) A system for obtaining an answer satisfying the join predicate by executing a Cartesian operation for each relation.
But as explained above, it is still probable that reference to unwanted data will still occur, resulting in an undue limitation in the operation speed.